/*
题目: 数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

https://leetcode.cn/problems/number-of-digit-one/
 */
public class CountDigitOne {
    int[][] memo = null;
    char[] cs = null;
    int size ;

    public int countDigitOne(int n) {
        cs = String.valueOf(n).toCharArray();
        size = cs.length;
        // 当前为 i 位置的时候, 表示现在有 j 个 1, 一维容量取决于题目, 到 i 下标的时候有多少  符合题意的状态
        memo = new int[size][10];

        // 初始化记忆化数组
        for (int i = 0; i < size; i ++)
            Arrays.fill(memo[i], -1);

        return dfs(0, 0, true);
    }

    // 当前到第 i 位了, 目前 1 的个数为 num , limited 表 是否受限
    private int dfs(int pos, int num, boolean limited) {
        if (pos >= size) {
            return num;
        }

        if (!limited && memo[pos][num] != -1) {
            return memo[pos][num];
        }

        int src = 0;
        for (int i = 0, up = limited ? cs[pos] - '0' : 9; i <= up; i ++) {
            src += dfs(pos + 1, num + (i == 1 ? 1 : 0), limited && i == up);
        }

        if (!limited) {
            memo[pos][num] = src;
        }
        return src;
    }
}
